贪心

定义

贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。

1. 从某个初始解出发；
2. 采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
3. 将所有解综合起来。

示例

找零钱

问题描述

假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？

解题思路

1. 找给顾客 sum_money=41 分钱，可选择的是 25 分、10 分、5 分和 1 分四种硬币。能找 25 分的，不找 10 分的原则，初次先找给顾客 25 分；
2. 还差顾客 sum_money=41-25=16。然后从 25 分、10 分、5 分和 1 分四种硬币选取局部最优的给顾客，也就是选 10 分的，此时 sum_money=16-10=6。重复迭代过程，还需要 sum_money=6-5=1,sum_money=1-1=0。至此，顾客收到零钱，交易结束；
3. 此时 41 分，分成了 1 个 25，1 个 10，1 个 5，1 个 1，共四枚硬币。

参考代码

sum_money=41
num_25=0
num_10=0
num_5=0
num_1=0
while sum_money >= 25:
    num_25 += 1;
    sum_money -= 25
while sum_money >=10:
    num_10 += 1;
    sum_money -= 10
while sum_money >= 5:
    num_5 += 1;
    sum_money -= 5
while sum_money >= 1:
    num_1 += 1;
    sum_money -= 1
print('25:',num_25)
print('10:',num_10)
print('5:',num_5)
print('1:',num_1)

总结

因此，贪心算法通常是自顶向下地做出贪心选择，不断地将给定的问题实例归约为更小的问题。贪心算法划分子问题的结果，通常是仅存在一个非空的子问题。

练习